package middle;

import java.util.ArrayList;
import java.util.List;

public class Solution_394 {

    public static void main(String[] args) {
        Solution_394 model = new Solution_394();
        System.out.println(model.decodeString("3[a]2[bc]"));
        System.out.println(model.decodeString("3[a2[c]]"));
        System.out.println(model.decodeString("2[abc]3[cd]ef"));
        System.out.println(model.decodeString("abc3[cd]xyz"));
        System.out.println(model.decodeString("abc3[de2[fg]do]a2[zz]cc"));
    }

    private int index = 0;
    public String decodeString(String s) {
        StringBuilder builder = new StringBuilder();
        this.index = 0;
        List<Character> list = dps(s.toCharArray());
        for (Character c : list) {
            builder.append(c);
        }
        return builder.toString();
    }

    private List<Character> dps(char[] chars) {
        List<Character> list = new ArrayList<>();
        int num = 0;
        for (; index < chars.length;) {
            char c = chars[index++];
            if (c >= '0' && c <= '9') {
                num = num * 10 + (c - '0');
            } else if (c == '[') {
                List<Character> dps = dps(chars);
                for (int j = 0; j < num; j++) {
                    list.addAll(dps);
                }
                num = 0;
            } else if (c == ']') {
                break;
            } else {
                list.add(c);
            }
        }
        return list;
    }
}
